package other;

public class canPartition_416 {
    public boolean canPartition(int[] nums) {
        //作为背包问题处理，nums内的数字相当于价值和重量
        //去填满大小为 sum/2 的背包
        int sum = 0;
        for (int i : nums)
            sum += i;
        if (sum % 2 != 0) return false;   //奇数无法分割
        int[] dp = new int[sum / 2 + 1]; // 容量为 j 的背包，所背的物品价值最大可以为 dp[j] ,若dp[j]==j ,即代表容量等于价值
        //使用滚动数组，即因为每一次只会上到上一行的数据，可以缩小到一维
        for (int i = 0; i < nums.length; i++) {  //遍历物品
            for (int j = sum / 2; j >= nums[i]; j--) {
                //当容量不够装下当前数字，直接用老数据，不进行更新
                //从后往前是因为，前面的老数据后边还要用，不能被覆盖
                //而后边的老数据，不会被前面的数据用到
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                //dp[j]为不装当前数字的情况（老数据）
                //dp[ j-nums[i] ] +nums[i] 为装当前数字的情况
            }
            if (dp[sum/2] == sum / 2)   //容量为sum/2的背包可以被满时直接返回
                return true;
        }
        return false;
    }

}
